package lin.zhihong.redme.algorithm;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Homework2 {

    public static void main(String[] args) {

        try (InputStream resourceAsStream = Homework1.class.getClassLoader().getResourceAsStream("homework2.data");
             BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(resourceAsStream))) {
            while (bufferedReader.ready()) {
                String s = bufferedReader.readLine();

                String[] arrays = s.split(";");
                Integer[] workers =
                        Arrays.asList(arrays[0].split(",")).stream().map(new Function<String, Integer>() {
                            @Override
                            public Integer apply(String s) {
                                return Integer.valueOf(s);
                            }
                        }).collect(Collectors.toList()).toArray(new Integer[0]);
                Integer[] golds =
                        Arrays.asList(arrays[1].split(",")).stream().map(new Function<String, Integer>() {
                            @Override
                            public Integer apply(String s) {
                                return Integer.valueOf(s);
                            }
                        }).collect(Collectors.toList()).toArray(new Integer[0]);
                System.out.println("金矿: " + arrays[1]);
                System.out.println("人数: " + arrays[1]);
                int bestGoldMining = getBestGoldMining(10, arrays.length, golds, workers, new HashSet<>());
                System.out.printf("黄金总和: " + bestGoldMining);
            }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public static int getBestGoldMining(int populations, int mines, Integer[] golds, Integer[] workers, Set<Integer> digs) {

        if (populations == 0 || mines == 0) {
            return 0;
        }

        if (populations < workers[mines - 1]) {
            return getBestGoldMining(populations, mines-1, golds, workers, digs);
        }

        //挖当前金矿
        int dig = getBestGoldMining(populations - workers[mines - 1], mines-1, golds, workers, digs) + golds[mines - 1];

        //不挖当前金矿
        int notDig = getBestGoldMining(populations, mines-1, golds, workers, digs);

        int max = dig;
        if (max < notDig) {
            max = notDig;
        } else {
            if (!digs.contains(mines)) {
                System.out.println("挖第" + mines + "座金矿，黄金" + golds[mines - 1] + "克");
                digs.add(mines);
            }
        }

        return max;
    }
}
